This application is directed to similar subject matter as commonly assigned U.S. patent application Ser. No. 09/506,230 entitled “APPARATUS AND METHOD FOR DISPATCHING FIXED PRIORITY THREADS USING A GLOBAL RUN QUEUE IN A MULTIPLE RUN QUEUE SYSTEM” filed on Feb. 17, 2000, U.S. patent application Ser. No. 09/506,856 entitled “APPARATUS AND METHOD FOR STARVATION LOAD BALANCING USING A GLOBAL RUN QUEUE IN A MULTIPLE RUN QUEUE SYSTEM” filed on Feb. 17, 2000, now U.S. Pat. No. 6,748,593, and U.S. patent application Ser. No. 09/506,231 entitled “APPARATUS AND METHOD FOR PERIODIC LOAD BALANCING IN A MULTIPLE RUN QUEUE SYSTEM”, filed on Feb. 17, 2000, now U.S. Pat. No. 6,658,449, which are hereby incorporated by reference in their entirety.
1. Technical Field
The invention is generally directed to an improved computing system. More specifically, the present invention is directed to mechanisms for load balancing of fixed priority threads in a multiple run queue environment.
2. Description of Related Art
Multiple processor systems are generally known in the art. In a multiple processor system, a process may be shared by a plurality of processors. The process is broken up into threads which may be processed concurrently. However, the threads must be queued for each of the processors of the multiple processor system before they may be executed by a processor.
One known technique for queuing threads to be dispatched by a processor in a multiple processor system is to maintain a single centralized queue, or “run queue.” As processors become available, they take the next thread in the queue and process it. The drawback to this approach is that the centralized queue becomes a bottleneck for the threads and processing time may be lost due to processors spinning on a run queue lock, i.e. becoming effectively idle, while waiting to take the next thread from the centralized queue.
Another known technique for queuing threads is to maintain separate queues for each processor. Thus, when a thread is created, it is assigned to a processor in some fashion. With such a technique, some processors may become overloaded while other processors are relatively idle. Furthermore, some low priority threads may become starved, i.e. are not provided with any processing time, because higher priority threads are added to the run queue of the processor for which the low priority threads are waiting.
In addition to the above, system administrators (or privileged programs) may apply a fixed priority scheduling policy by which each program's scheduling priority is set to a constant value. In such policies, lower numerial priority requests receive unconditionally better service (faster execution) than higher numbered priorities, for example, without regard to resource consumption by the running program's threads. This means that if, for example, four fixed priority threads were created with respective priorities of 30, 30, 31 and 31, the system should attempt to favor the two priority 30 threads over the two priority 31 threads.
On uniprocessor (UP) computer systems and multiprocessor (MP) computer systems with a single run queue, the desired prioritization happens automatically because all resource providers, e.g., central processing units (cpus), search the same run queue and that run queue is sorted by priority. However, with the advent of the multiple run queue support, this is no longer guaranteed.
To illustrate the problem, returning to the example above, if we assume a two way MP system, it would be desirable to have one of each priority 30 and 31 threads assigned to the local run queue for each processor:
Processor01Run queue:30303131
Such an arrangement would guarantee that whenever a priority 30 is runnable, i.e. available to be executed, it will run immediately in preference to the priority 31 threads. However, there currently is no mechanism that can reliably ensure such optimal arrangements of fixed priority threads. Rather, in many cases, fixed priority threads may be assigned to run queues in a non-optimal manner:
Processor01Run queue:30313031
When this occurs, the second priority 30 thread is waiting for processor 0 while a priority 31 thread runs on processor 1. Existing load balancing algorithms do not provide any mechanism for improving this situation such that the priority 30 threads are executed before the priority 31 threads.
Thus, there is a need for new technology to provide apparatus and methods for load balancing with regard to fixed priority threads in a multiple run queue system.